package com.hisen.algorithm.sort;

public class QuickSort {

    /**
     * 快速排序
     *
     * @param numArr 要排序的数组
     * @param left   开始排序的下标
     * @param right  结束排序的下标
     * @return 排序后的数组
     */
    public static int[] sort(int[] numArr, int left, int right) {
        int centerIndex = qSort(numArr, left, right);
        qSort(numArr, left, centerIndex - 1);
        qSort(numArr, centerIndex + 1, right);
        return numArr;
    }

    private static int qSort(int[] numArr, int left, int right) {
        int base = numArr[left];
        int start = left;
        left++;
        while (left != right) {
            while (numArr[right] >= base && left < right) {
                right--;
            }
            while (numArr[left] <= base && left < right) {
                left++;
            }
            if (left < right) {
                swap(numArr, left, right);
            }
        }
        swap(numArr, left, start);
        return left;
    }

    private static void swap(int[] numArr, int left, int right) {
        int temp = numArr[left];
        numArr[left] = numArr[right];
        numArr[right] = temp;
    }
}
